package com.zhupf.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2023年12月26日 15:50
 * @Description
 * 39. 组合总和
 *
 */
public class CombinationSum {

    private static List<List<Integer>> ans = new ArrayList<>();

    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        combinationSum(candidates,7);
    }

    public  static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        dfs(0,target,candidates,0,path);
        return ans;
    }

    public static void dfs(int idx,int target,int[] candidates,int sum,List<Integer> path){
        if(target == sum){
            ans.add(new ArrayList<>(path));
            return;
        }
        if(sum > target){
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            sum +=candidates[i];
            path.add(candidates[i]);
            dfs(i,target,candidates,sum,path);
            sum -= candidates[i];
            path.remove(path.size()-1);
        }
    }

}
